/**
 * @author ghp
 * @date 2023/5/30
 * @title 复习深度搜索DFS
 * @description 求 n 位数的全排列的种类
 */
public class DFSTest {
    public static void main(String[] args) {
        int n = 3;
        int[] path = new int[n];
        boolean[] vis = new boolean[n];
        dfs(0, path, vis);
    }


    private static void dfs(int step, int[] path, boolean[] vis) {
        if (step >= path.length) {
            // 已经遍历到第n个元素了
            for (int i = 0; i < path.length; i++) {
                System.out.print(path[i] + " ");
            }
            System.out.println();
        }
        for (int i = 0; i < path.length; i++) {
            if (!vis[i]) {
                path[step] = i + 1;
                vis[i] = true;
                dfs(step+1, path, vis);
                // 恢复现场
                vis[i] = false;
            }
        }
    }

}
